#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

 

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：

输入：s = "0000"
输出：["0.0.0.0"]
示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
执行用时：
4 ms
, 在所有 C++ 提交中击败了
39.84%
的用户
内存消耗：
6.5 MB
, 在所有 C++ 提交中击败了
44.34%
的用户
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//todo 第一天写的时候 没有开vector<string> temp; 思路有点乱 。反正错了 今早秒了
//看到别人是插入逗号的 然后回溯删除逗号 。我原来没有那么想 反正啊 效率不高反正是过了
vector<string> ret;
vector<string> temp;

// 算是 回溯中的分割问题
void restoreIpAddressesT(string &s, string snow, int startIndex, int size) {
    if (temp.size() > 4 || snow.size() > 3)
        return;

    if (snow.size() == 3 && snow.compare("255") > 0)
        return;


    if (temp.size() == 4 && size == s.size()) {
        string t = "";
        for (int i = 0; i < 4; ++i) {
            t = t + temp[i] + ".";
        }
        t.pop_back();
        ret.push_back(t);
        return;
    }


    for (int i = startIndex; i < s.size(); ++i) {
        string s1 = s.substr(startIndex, i - startIndex + 1);
        //开始为0直接for过滤
        if (s1[0] == '0' && s1.size() > 1)
            continue;
        temp.push_back(s1);
        restoreIpAddressesT(s, s1, i + 1, size + s1.size());
        temp.pop_back();

    }


}

vector<string> restoreIpAddresses(string s) {

    restoreIpAddressesT(s, "", 0, 0);
    return ret;
}